| contributor | Theoretische Informatik (IFI) |
| creator | Diekert, Volker |
| date | 1998-03 |
| description | 43 pages |
| This report is a preliminary version of the twelfth chapter in the forthcoming book of M.~Lothaire {\em Algebraic Combinatorics on Words}. The aim is to describe a self-contained proof of a fundamental result of Makanin (1977), which solves the satisfiability problem of equations with constants over free monoids. The presentation of Makanin's algorithm is based on a generalization due to Schulz (1990), where Makanin's result is extended to the case where solutions are restricted by imposing regular constraints on the variables. | |
| format | application/pdf |
| identifier | http://www.informatik.uni-stuttgart.de/cgi-bin/NCSTRL/NCSTRL_view.pl?id=TR-1998-02&engl=1 |
| language | eng |
| publisher | Stuttgart, Germany, Universität Stuttgart |
| relation | Technical Report No. 1998/02 |
| source | ftp://ftp.informatik.uni-stuttgart.de/pub/library/ncstrl.ustuttgart_fi/TR-1998-02/TR-1998-02.pdf |
| subject | Nonnumerical Algorithms and Problems (CR F.2.2) |
| Formal Languages (CR F.4.3) | |
| Makanin | |
| Makanins's Algorithm | |
| Word Equations | |
| Regular Constraints | |
| title | Makanin's Algorithm for Solving Word Equations with Regular Constraints |
| type | Text |
| Technical Report |